package com.apkcore.bl;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/open-the-lock/submissions/
 */
public class _752打开转盘锁 {
    public static void main(String[] args) {
        String[] deadends = {"0201", "0101", "0102", "1212", "2002"};
        String taget = "0202";
        System.out.println(new _752打开转盘锁().openLock(deadends, taget));
    }

    public int openLock2(String[] deadends, String target) {
        Queue<String> queue = new LinkedList<>();
        Set<String> set = new HashSet<>();
        queue.offer("0000");
        set.add("0000");
        Set<String> deadSets = new HashSet<>();
        Collections.addAll(deadSets, deadends);
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
//                if (cur == null) {
//                    continue;
//                }

                if (deadSets.contains(cur)) {
                    continue;
                }
                if (target.equals(cur)) {
                    return step;
                }

                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!set.contains(up)) {
                        queue.offer(up);
                        set.add(up);
                    }
                    String down = subOne(cur, j);
                    if (!set.contains(down)) {
                        queue.offer(down);
                        set.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9') {
            ch[j] = '0';
        } else {
            ch[j] += 1;
        }
        return new String(ch);

    }

    String subOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '0') {
            ch[j] = '9';
        } else {
            ch[j] -= 1;
        }
        return new String(ch);
    }

    /**
     * 双向BFS
     */
    public int openLock1(String[] deadends, String target) {
        Queue<String> queue1 = new LinkedList<>();
        Queue<String> queue2 = new LinkedList<>();
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();
        queue1.offer("0000");
        set1.add("0000");
        queue2.offer(target);
        set2.add(target);
        Set<String> deadSets = new HashSet<>();
        Collections.addAll(deadSets, deadends);
        int step = 0;
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            int size = queue1.size();
            for (int i = 0; i < size; i++) {
                String cur = queue1.poll();

                if (cur == null || deadSets.contains(cur)) {
                    continue;
                }
                if (set2.contains(cur)) {
                    return step;
                }

                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!set1.contains(up)) {
                        queue1.offer(up);
                        set1.add(up);
                    }
                    String down = subOne(cur, j);
                    if (!set1.contains(down)) {
                        queue1.offer(down);
                        set1.add(down);
                    }
                }
            }
            if (queue1.size() > queue2.size()) {
                Queue<String> temp = queue1;
                queue1 = queue2;
                queue2 = temp;
                Set<String> tempp = set1;
                set1 = set2;
                set2 = tempp;
            }
            step++;
        }
        return -1;
    }


    /**
     * 双向BFS
     */
    public int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>(Arrays.asList(deadends));
        // 用集合不用队列，可以快速判断元素是否存在
        Set<String> q1 = new HashSet<>();
        Set<String> q2 = new HashSet<>();
        Set<String> visited = new HashSet<>();

        int step = 0;
        q1.add("0000");
        q2.add(target);

        while (!q1.isEmpty() && !q2.isEmpty()) {
            // 哈希集合在遍历的过程中不能修改，用temp存储扩散结果
            Set<String> temp = new HashSet<>();

            // 将q1中的所有节点向周围扩散
            for (String cur : q1) {
                // 判断是否到达终点
                if (deads.contains(cur)) {
                    continue;
                }
                if (q2.contains(cur)) {
                    return step;
                }
                visited.add(cur);

                // 将一个节点的未遍历相邻节点加入集合
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        temp.add(up);
                    }
                    String down = subOne(cur, j);
                    if (!visited.contains(down)) {
                        temp.add(down);
                    }
                }
            }
            // 在这里增加步数
            step++;
            // temp相当于q1
            // 这里交换q1 q2，下一轮while就是扩散q2
            if (q1.size() > q2.size()) {
                q1 = q2;
                q2 = temp;
            } else {
                q1 = temp;
            }
        }

        return -1;
    }
}
